/**
		TRABALHO 2 DA DISCIPLINA SSC0143-PROGRAMACAO CONCORRENTE

		Jhonata Pereira Martins          7656637           
		Normandis Jose Santos Jr.        7656540
		Rafael Araujo de Oliveira        7704971  


							VERSAO SEQUENCIAL

*/

#include <stdio.h>
#include <limits.h>


#define N 1000
#define INF INT_MAX

//matriz de adjacencia
int graph[N][N];

//matriz com as distancias do vertice i para o vertice j(independente se ha uma aresta direta entra o vertice i e o j1)
int matriz_distancias[N][N];

//funcao para procurar o vertice com a minima distancia do vertice src
int mindistance(int src, int n, int *visitados)
{
	// inicializa o valor minimo
	int min = INF, min_index;
	int v;
	for (v = 0; v < n; v++)
	{	
		if (visitados[v] == 0 && matriz_distancias[src][v] <= min)
		{
			min = matriz_distancias[src][v];
			min_index = v;
		}
	}
	return min_index;
}


//implementacao de dijkstra para encontrar o menor caminho entre o vertice src e todos os outros vertices
void dijkstra(int src, int n)
{
	int i;
	//vetor de visitados
    int visitados[n];
	//inicializa os visitados
	for (i = 0; i < n; i++)
	{
		visitados[i] = 0;
	}

	int count;
	// encontra o menor caminho de src para todos os vertices
	for (count = 0; count < n-1; count++)
	{
		//escolhe o vertice com a minima distancia. Na primeira iteracao eh sempre o vertice src
		int u = mindistance(src, n, visitados);

		//marca o vertice como visitado
		visitados[u] = 1;

		int v;
		//Atualiza o valor na matriz de distancias dos vértices adjacentes do vértice escolhido.
		for (v = 0; v < n; v++)
		{			
			if (!visitados[v] && graph[u][v] && matriz_distancias[src][u] != INF && matriz_distancias[src][u]+graph[u][v] < matriz_distancias[src][v])
			{
				matriz_distancias[src][v] = matriz_distancias[src][u] + graph[u][v];
				matriz_distancias[v][src] = matriz_distancias[src][v];
			}
		}
	}

}

//metodo para inicializar a matriz de adjacencia e a matriz de distancias
void init(int n)                       
{
	int i, j;
	for(i = 0; i < n; i++)
	{
		for(j = 0; j < n; j++)
		{
			graph[i][j] = 0;
			matriz_distancias[i][j] = INF;
		}
		matriz_distancias[i][i] = 0;
	}
}



//metodo que mostra o valor da maior distancia do vertice escolhido para ser a localizacao do hospital
void melhor_ponto(int n)
{

	int dist[N];
	int i, j, maior, menor = INF, idx;

	for(i = 0; i < n; i++)
	{
		maior = 0;
		for(j = 0; j < n; j++)
		{
			if(matriz_distancias[i][j] > maior)
			{
				maior = matriz_distancias[i][j];	
				dist[i] = maior;			
			}
		}
		if(maior < menor && dist[i] != 0)
		{
			menor = dist[i];
			idx = i;
		}
	}

	for(i = 0; i < n;i++)
	{
		if(dist[i] < menor && dist[i] != 0)
		{
			menor = dist[i];
			idx = i;
		}
	}

	printf("Vertice %d. Distancia maxima: %d\n", idx, dist[idx]);

}

int main()
{
	int n, m, a, b, i;
	//lendo os dados e inicializando a matriz de adjacencia e a matriz de distancias
	scanf("%d %d ", &n, &m);
	init(n);
	for(i = 0; i < m; i++)
	{
		scanf("%d %d ", &a, &b);
		scanf("%d ", &graph[a-1][b-1]);
		graph[b-1][a-1] = graph[a-1][b-1];
	}

	//executando dikstra para cara vertice e depois selecionando o vertice onde ficara o hospital	
	for(i = 0; i < n; i++)
	{
		dijkstra(i, n);
	}
	melhor_ponto(n);	

	return 0;
}
